A nested loop join is a naive
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
that joins two sets by using two nested
loop
Loop or LOOP may refer to:
Brands and enterprises
* Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live
* Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets
* Loop Mobile, an ...
s. Join operations are important for
database
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
management.
Algorithm
Two relations
and
are joined as follows:
algorithm nested_loop_join is
for each tuple ''r'' in ''R'' do
for each tuple ''s'' in ''S'' do
if ''r'' and ''s'' satisfy the join condition then
yield tuple <''r'',''s''>
This algorithm will involve n
r*b
s+ b
r block transfers and n
r+b
r seeks, where b
r and b
s are number of blocks in relations R and S respectively, and n
r is the number of tuples in relation R.
The algorithm runs in
I/Os, where
and
is the number of tuples contained in
and
respectively and can easily be generalized to join any number of relations ...
The
block nested loop
A block-nested loop (BNL) is an algorithm used to join two relations in a relational database.
This algorithm is a variation of the simple nested loop join and joins two relations R and S (the "outer" and "inner" join operands, respectively). Sup ...
join algorithm
[http://www.databaselecture.com/slides/9_Operator_Implementations.pdf ] is a generalization of the simple nested loops algorithm that takes advantage of additional
memory
Memory is the faculty of the mind by which data or information is encoded, stored, and retrieved when needed. It is the retention of information over time for the purpose of influencing future action. If past events could not be remembered, ...
to reduce the number of times that the
relation is scanned. It loads large chunks of relation R into main memory. For each chunk, it scans S and evaluates the join condition on all tuple pairs, currently in memory. This reduces the number of times S is scanned to once per chunk.
Index join variation
If the inner relation has an index on the attributes used in the join, then the naive nest loop join can be replaced with an index join.
algorithm index_join is
for each tuple ''r'' in ''R'' do
for each tuple ''s'' in ''S'' in the index lookup do
yield tuple <''r'',''s''>
The time complexity for this variation improves from
See also
*
Hash join
The hash join is an example of a join algorithm and is used in the implementation of a relational database management system. All variants of hash join algorithms involve building hash tables from the tuples of one or both of the joined relations ...
*
Sort-merge join
The sort-merge join (also known as merge join) is a join algorithm and is used in the implementation of a relational database management system.
The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the ...
References
Join algorithms
{{compu-sci-stub